package leetcode.code2018;

import leetcode.IDebug;

public class Solution implements IDebug {

	int m, n;
	char[][] board;
	char[] cs;
	int len;

	public boolean placeWordInCrossword(char[][] board, String word) {
		cs = word.toCharArray();
		len = cs.length;
		m = board.length;
		n = board[0].length;
		this.board = board;
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				char cur = board[i][j];
				if (cur == cs[0] || cur == ' ') {
					// 从上到下，该单词上边和下边 相邻 格子不能为 ' ' 或小写英文字母
					if (isEdge(i - 1, j) && i + len - 1 < m && isEdge(i + len, j) && this.down(i, j)) {
						return true;
					}
					// 下到上
					if (isEdge(i + 1, j) && i - len + 1 >= 0 && isEdge(i - len, j) && this.up(i, j)) {
						return true;
					}
					// 左到右
					if (isEdge(i, j - 1) && j + len - 1 < n && isEdge(i, j + len) && this.right(i, j)) {
						return true;
					}
					// 右到左
					if (isEdge(i, j + 1) && j - len + 1 >= 0 && isEdge(i, j - len) && this.left(i, j)) {
						return true;
					}
				}
			}
		}
		return false;
	}

	private boolean right(int x, int y) {
		return this.leftRight(x, y, 1);
	}

	private boolean left(int x, int y) {
		return this.leftRight(x, y, -1);
	}

	private boolean up(int x, int y) {
		return this.updown(x, y, -1);
	}

	private boolean down(int x, int y) {
		return this.updown(x, y, 1);
	}

	private boolean isEdge(int i, int j) {
		if (i >= 0 && i < m && j >= 0 && j < n) {
			if (this.board[i][j] == '#') {
				return true;
			} else {
				return false;
			}
		}
		return true;
	}

	private boolean updown(int x, int y, int d) {
		for (int i = x, p = 0; p < len; i += d, p++) {
			char cur = this.board[i][y];
			// 该单词不占据任何 '#' 对应的格子。
			if (cur == '#') {
				return false;
			}
			// 每个字母对应的格子要么是 ' ' （空格）
			if (cur == ' ') {
				continue;
			}
			// 要么与 board 中已有字母 匹配
			if (cur != this.cs[p]) {
				return false;
			}
		}
		return true;
	}

	private boolean leftRight(int x, int y, int d) {
		for (int i = y, p = 0; p < len; i += d, p++) {
			char cur = this.board[x][i];
			// 该单词不占据任何 '#' 对应的格子。
			if (cur == '#') {
				return false;
			}
			// 每个字母对应的格子要么是 ' ' （空格）
			if (cur == ' ') {
				continue;
			}
			// 要么与 board 中已有字母 匹配
			if (cur != this.cs[p]) {
				return false;
			}
		}
		return true;
	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
